package Test;
//三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。
// 实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
//示例 1：
// 输入：n = 3
// 输出：4
// 说明：有四种走法
//示例 2：
// 输入：n = 5
// 输出：13
//提示:
//n 范围在[1, 1000000]之间
public class test03 {

    class Solution {
        public int waysToStep(int n) {
            //1.创建dp表
            //2.初始化
            //3.填表
            //4.返回值

            int MOD = (int)1e9 + 7;
            //处理边界情况
            if(n == 1|| n == 2)return n;
            if(n == 3)return 4;
            int []dp = new int[n + 1];
            dp[1] = 1;dp[2] = 2 ;dp[3] = 4;
            for(int i  = 4; i <= n; i++){
                dp[i] = ((dp[i - 3] + dp[i - 2] )%MOD+ dp[i - 1])%MOD;
            }
            return dp[n];
        }
    }
}
